/*
https://leetcode-cn.com/problems/trapping-rain-water-ii/solution/jie-yu-shui-ii-by-leetcode-solution-vlj3/
 */
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution407 {
    public int trapRainWater(int[][] heightMap) {
        int m=heightMap.length;
        int n=heightMap[0].length;
        if (m<=2||n<=2){
            return 0;
        }
        boolean[][] visit=new boolean[m][n];
        PriorityQueue<int[]> queue=new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (i==0||i==m-1||j==0||j==n-1){
                    visit[i][j]=true;
                    queue.offer(new int[]{i*n+j,heightMap[i][j]});
                }else{
                    visit[i][j]=false;
                }
            }
        }
        int ans=0;
        int[] dirs=new int[]{-1,0,1,0,-1};
        while (!queue.isEmpty()){
            int[] cur=queue.poll();
            for (int k=0;k<4;k++){
                int x=cur[0]/n+dirs[k];
                int y=cur[0]%n+dirs[k+1];
                if (x>=0 && x<m && y>=0 && y<n && !visit[x][y]){
                    ans=ans+Math.max(0,cur[1]-heightMap[x][y]);
                    queue.offer(new int[]{x*n+y,Math.max(heightMap[x][y],cur[1])});
                    visit[x][y]=true;
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution407().trapRainWater(new int[][]{{1,4,3,1,3,2},{3,2,1,3,2,4},{2,3,3,2,3,1}}));
    }
}
